package Solutions;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * @Classname SmallestSubsequenceOfDistinctCharacters
 * @Description TODO
 * @Date 2021/3/6 19:28
 * @Created by ASUS
 */
public class SmallestSubsequenceOfDistinctCharacters {

    public String smallestSubsequence(String s) {
        Stack<Integer> stack = new Stack<>();
        int[] lastIndex = new int[128];// 用于记录每个字符最后出现的位置，可以理解为一个简单的 map

        // mark the index of a character that appears recently.
        for (int i = 0; i < s.length(); i++) {
            lastIndex[s.charAt(i)] = i;
        }

        Set<Integer> set = new HashSet<>();// 用于去重

        for (int i = 0; i < s.toCharArray().length; i++) {
            int character = s.charAt(i);
            if (set.contains(character)) continue;// 字符在栈中已经出现过一次了
            while (!stack.isEmpty() && character < stack.peek() && i < lastIndex[stack.peek()]) {
                set.remove(stack.pop());
            }
            set.add(character);
            stack.push(character);

        }
        StringBuilder sb = new StringBuilder();
        for (int i : stack) {
            sb.append((char) i);
        }
//        while (!stack.isEmpty()) {
//            sb.append((char)stack.pop().intValue());
//        }


        return sb.toString();
    }

    public String smallestSubsequence_(String s) {
        if (s == null || s.length() <= 2) {
            return s;
        }

        StringBuilder sb = new StringBuilder(s);
        for (int i = 0; i < s.length(); i++) {

        }


        return null;
    }

    public static void main(String[] args) {
        System.out.println(new SmallestSubsequenceOfDistinctCharacters().smallestSubsequence("bcabc"));
    }
}
